"""105. 从前序与中序遍历序列构造二叉树"""


# 链接：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solutions/255811/cong-qian-xu-yu-zhong-xu-bian-li-xu-lie-gou-zao-9/
from typing import List


class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        def myBuildTree(
            preorder_left: int,
            preorder_right: int,
            inorder_left: int,
            inorder_right: int,
        ):
            # 前序遍历的左边界 > 右边界
            if preorder_left > preorder_right:
                return None

            # 前序遍历中的第一个节点就是根节点，preorder_root表示的是索引
            preorder_root = preorder_left
            # inorder_root是找到在中序遍历里卖弄的索引，注意这里是因为题中说没有重复才敢这么写）（这里就体现了用字典提前做好的好处）
            inorder_root = index[preorder[preorder_root]]

            # 先把根节点建立出来，力扣里面有TreeNode的定义的
            root = TreeNode(preorder[preorder_root])

            # 根据中序得到左子树中的节点数目
            size_left_subtree = inorder_root - inorder_left
            # 递归地构造左子树，并连接到根节点
            # 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
            root.left = myBuildTree(
                preorder_left + 1,
                preorder_left + size_left_subtree,
                inorder_left,
                inorder_root - 1,
            )
            # 递归地构造右子树，并连接到根节点
            # 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
            root.right = myBuildTree(
                preorder_left + size_left_subtree + 1,
                preorder_right,
                inorder_root + 1,
                inorder_right,
            )
            return root

        # 从这里开始
        n = len(preorder)
        # 构造哈希映射，帮助我们快速定位根节点
        index = {element: i for i, element in enumerate(inorder)}
        return myBuildTree(0, n - 1, 0, n - 1)


# 尝试模仿
from typing import List, Optional

# # 定义二叉树节点类（还是用力扣的）
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right


class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        def myBuildTree(
            preorder_left: int,
            preorder_right: int,
            inorder_left: int,
            inorder_right: int,
        ):
            if preorder_left > preorder_right:
                return None

            # 前序遍历中的第一个节点就是根节点
            preorder_root = preorder_left
            # 在中序遍历中定位根节点
            inorder_root = index[preorder[preorder_root]]

            # 先把根节点建立出来
            root = TreeNode(preorder[preorder_root])
            # 得到左子树中的节点数目
            size_left_subtree = inorder_root - inorder_left

            # 递归地构造左子树，并连接到根节点
            root.left = myBuildTree(
                preorder_left + 1,
                preorder_left + size_left_subtree,
                inorder_left,
                inorder_root - 1,
            )
            # 递归地构造右子树，并连接到根节点
            root.right = myBuildTree(
                preorder_left + size_left_subtree + 1,
                preorder_right,
                inorder_root + 1,
                inorder_right,
            )
            return root

        n = len(preorder)
        # 构造哈希映射，帮助我们快速定位根节点
        index = {element: i for i, element in enumerate(inorder)}
        return myBuildTree(0, n - 1, 0, n - 1)


# 帮助函数：层次遍历打印二叉树
def treeNodeToList(root: TreeNode) -> List[Optional[int]]:
    if not root:
        return []

    result = []
    queue = [root]

    while queue:
        node = queue.pop(0)
        if node:
            result.append(node.val)
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append(None)

    # 去掉结果列表最后多余的 None 值
    while result and result[-1] is None:
        result.pop()

    return result


# preorder1 = [3, 9, 20, 15, 7]
# inorder1 = [9, 3, 15, 20, 7]
# solution = Solution()
# root1 = solution.buildTree(preorder1, inorder1)
# print(treeNodeToList(root1))

# preorder2 = [-1]
# inorder2 = [-1]
# root2 = solution.buildTree(preorder2, inorder2)
# print(treeNodeToList(root2))
